package com.lw.leetcode.bit.b;

/**
 * Created with IntelliJ IDEA.
 * b
 * bit
 * 2550. 猴子碰撞的方法数
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/29 13:45
 */
public class MonkeyMove {

    public static void main(String[] args) {
        MonkeyMove test = new MonkeyMove();

        // 6
//        int n = 3;

        // 14
//        int n = 4;

        // 140624999
//        int n = 1000000000;

        // 140624999
        int n = 500000003;

        int i = test.monkeyMove(n);
        System.out.println(i);
    }

    public int monkeyMove(int n) {
        long item = 2;
        long sum = 1;
        while (n != 0) {
            if ((n & 1) == 1) {
                sum = (sum * item) % 1000000007;
            }
            item = (item * item) % 1000000007;
            n >>= 1;
        }
        return (int) (sum - 2 < 0 ? sum - 2 + 1000000007 : sum - 2);
    }

}
